16. 城市聚集度

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

class UnionFindSet {
    constructor(n) {
        this.father = new Array(n);
        for(let i=0; i<n; i++) {
            this.father[i] = i;
        }
    }

    find(x) {
        if (this.father[x] !=== x) {
            this.father[x] = this.find(this.father[x]);
        }
        return this.father[x];
    }

    unionSet(x, y) {
        const x_fa = this.find(x);
        const y_fa = this.find(y);
        if (x_fa !== y_fa) {
            this.father[y_fa] = x_fa;
        }
    }
}

let n;
let relations = [];

const lines = [];
rl.on('line', (line) => {
    if (!n) {
        n = parseInt(line);
    } else {
        const [x, y] = line.split(' ').map(Number);
        relations.push([x, y]);
    }
});
rl.on('close', () => {
    let min_dp = Infinity;
    let city = [];
    for(let i=1; i<=n; i++) {
        const ufs = new UnionFindSet(n+1);
        for(const [x,y] of relations) {
            if (x===i || y===i)continue;
            ufs.unionSet(x, y);
        }
        const count = new Map();
        for(let f of ufs.father) {
            f = ufs.find(f);
            count.set(f, (count.get(f) || 0) + 1);
        }

        let dp = 0;
        for(const c of count.values()) {
            dp = Math.max(dp, c);
        }

        if (dp < min_dp) {
            min_dp = dp;
            city = [i];
        } else if (dp === min_dp) {
            city.push(i);
        }
    }
    console.log(city.join(' '));
})